1. Field of the Invention
The present invention relates to a method and a program for determining an intersection point of a triangle with a line segment.
2. Description of the Related Art
Substantial data that includes shape data and physical property data integrated with each other can be stored with a small memory capacity. Thereby, data regarding a shape, a structure, a physical property and a history of an object can be managed in an integrated fashion, and data regarding a series of processes such as designing, machining, assembling, testing, and evaluating can be managed by the same data. Patent Literature 1 discloses a substantial data storing method by which a CAD and a simulation can be integrated. [Patent Literature 1] Japanese Laid-Open Patent Publication No. 2002-230054.
According to Patent Literature 1, as shown in FIG. 1, the method of storing substantial data configured from shape data and physical property data integrated with each other includes an external data input step (A), oct-tree division step (B), and a cell data storing step (C). In the external data input step (A), the external data 12 including the boundary data of the object is input to a computer or the like having a stored program for the method of the Patent Literature 1. This boundary data is obtained in an external data obtaining step S1. In the oct-tree division step (B), oct-tree division divides the external data 12 into rectangular parallelepiped cell of which boundary surfaces are perpendicular to each other. In the cell data storing step (C), various physical property values are stored for each cell.
According to the storing method of Patent Literature 1, the external data including the shape data of the object is divided into rectangular parallelepiped cells of which boundary surfaces are perpendicular to each other, and the various physical property values are stored for each cell. Each divided cell is classified into an internal cell or a boundary cell that includes the boundary surface. The internal cell contains one kind of physical property values as attribute, and the boundary cell contains two kinds of physical property values corresponding to the inside and the outside of the object, respectively.
Hereinbelow, the data used in the above method is referred to as “V-CAD data”, and designing and simulation using this data is referred to as “volume-CAD” or “V-CAD”. In FIG. 1, the reference numeral 14 designates V-CAD data.
FIG. 2 shows a flow of creating V-CAD data from external data according to the method of Patent Literature 1. As shown in FIG. 2, in STEP-1, a voxel space is defined for S-CAD data or a triangle patch data, and in STEP-2, intersection points of a geometric shape with the ridges of each cell are determined by calculation (that is, cell cut points are determined). In STEP-3, an outer circumferential loop of the cell internal surface is formed on the basis of the cut point data for each cell. In STEP-4, the inside of the outer circumferential loop are divided into triangles by referring to the original geometric shape. In STEP-5, the medium values of the cell are set. Thereby, the V-CAD data is formed.
In the method of Patent Literature 1, the intersection points of the triangle with the ridges of each cell need be repeatedly calculated a number of times. This triangle defines a geometric shape expressed by the external data.
Non-Patent Literatures 1 through 3 disclose conventionally known methods of calculating the intersection point of the triangle with the line segment.
[Non-Patent Literature 1]
Möller's method (Journal of graphics tools, 2(1): P21–28 1997).
[Non-Patent Literature 2]
Badouel's method (Graphic Gems, Academic Press P390–393 1990.
[Non-Patent Literature 3]
Computational Geometry in C: Joseph. O'Rourke/Cambridge University Press P239).
Various methods are used for calculating the intersection point of a triangle with a line segment. Many of these methods calculate the intersection of an infinite plane with an infinite line to determine whether or not the intersection point is positioned inside the triangle of the closed region on the plane. The calculation by these methods results in a high cost, and in the future in the field of the V-CAD system, it will be necessary to improve the calculation method in which calculation is repeatedly performed a number of times.
According to the Moller's method of Non-Patent Literature 1, a calculation cost can become relatively low by use of the vector calculation expressed by the following Equation (1) of Formula 2.
      [          Formula      ⁢                          ⁢      2        ]                                            [                                                            t                                                                              u                                                                              v                                                      ]                    =                                    [                                                                                                                  (                                                                                                                                            P                                1                                                            ⁢                                                              P                                Lin                                                                                      ⇀                                                    ×                                                                                                                    P                                1                                                            ⁢                                                              P                                2                                                                                      ⇀                                                                          )                                            ·                                                                                                    P                            1                                                    ⁢                                                      P                            3                                                                          ⇀                                                                                                                                                                                (                                                                              V                            Dir                                                    ×                                                                                                                    P                                1                                                            ⁢                                                              P                                3                                                                                      ⇀                                                                          )                                            ·                                                                                                    P                            1                                                    ⁢                                                      P                            Lin                                                                          ⇀                                                                                                                                                                                (                                                                                                                                            P                                1                                                            ⁢                                                              P                                Lin                                                                                      ⇀                                                    ×                                                                                                                    P                                1                                                            ⁢                                                              P                                2                                                                                      ⇀                                                                          )                                            ·                                                                                                    P                            1                                                    ⁢                                                      P                            Lin                                                                          ⇀                                                                                                        ]                        /                          (                                                (                                                            V                      Dir                                        ×                                                                                            P                          1                                                ⁢                                                  P                          3                                                                    ⇀                                                        )                                ·                                                                            P                      1                                        ⁢                                          P                      2                                                        ⇀                                            )                                                            (          1          )                    
P1, P2, P3, PLin: the triangle vertexes, the starting point of the line segment
VDir: a direction vector of the line segment
t: a parameter in the line segment
u and v: parameters in the triangle
However, in this method, even when calculating intersection points of plural different line segments with the same triangle, it is necessary to work out the equation repeatedly for each line segment. Accordingly, this method produces no merit for the intersection calculation on the same triangle, and cannot improve a calculation speed.
According to the Badouel's method of Non-Patent Literature 2, an intersection point is calculated by using a standard point PPln of a plane, a normal vector VNrm, and a standard point PLin of a line.
The distance between the standard point of the line and the plane is calculated by dst=VNrm·VPnt (VNrm is a unit vector), so that the coordinates of the intersection point are calculated by PInt=PLin+VLin·dst/(VLin·VNrm).
Subsequently, the respective triangle vertexes and the intersection point of the plane with the line are projected on any of coordinate planes (xy plane, yz plane and zx plane), and α and β in the equation (3) of Formula 3 are calculated on this projection plane.
In the case of the xy projection plane in FIG. 4, α and β are calculated by the inverse transformation of the linear transformation of the equation (4) of Formula 3 with P1(x1, y1, z1), P2(x2, y2, z2) and P3 (x3, y3, z3) and PInt (x, y, z), and with the z coordinates of each vertex being omitted.
      [          Formula      ⁢                          ⁢      3        ]                                            V            Pnt                    =                                                    P                Pin                            ⁢                              P                Lin                                      →                                                (          2          )                                                                                        P                1                ′                            ⁢                              P                Int                ′                                      →                    =                                                    α                ⁢                                                                  ⁢                                  P                  1                  ′                                ⁢                                  P                  2                  ′                                            →                        +                                          β                ⁢                                                                  ⁢                                  P                  1                  ′                                ⁢                                  P                  3                  ′                                            →                                                            (          3          )                                                          (                                                            x                                                                              y                                                      )                    =                                    [                                                                                                                  x                        2                                            -                                              x                        1                                                                                                                                                x                        3                                            -                                              x                        1                                                                                                                                                                                y                        2                                            -                                              y                        1                                                                                                                                                y                        3                                            -                                              y                        1                                                                                                        ]                        ⁢                          (                                                                    α                                                                                        β                                                              )                                                            (          4          )                    
There is following another inside/outside determination method of determining whether or not the intersection point is inside the triangle while this inside/outside determination method determines the intersection point of an infinite plane with a line by the same calculation as that of the Badouel's method.
According to an angle calculation method of Non-Patent Literature 3, in FIGS. 5A and 5B, inner product is calculated for each two of vectors extending from the intersection point to the respective vertexes. Then, it is determined whether or not the intersection point is inside the triangle on the basis of the calculated angle sum of 0 or 360 degrees. That is, in the case of FIG. 5A, the equation (5) can be established, and in the case of FIG. 5B, the equation (6) can be established.θ12+θ23+θ31=2PI  (5)θ12+θ23+θ31=0  (6)
Alternatively, as shown in FIGS. 6A and 6B, outer product is calculated for each two of the vectors from the intersection point to the respective vertexes by the equation (7) of Formula 4.
[Formula 4]VNrm12=V1×V2 VNrm23=V2×V3  (7)VNrm31=V3×V1 
In the case of FIG. 6A, VNrm12, VNrm23 and VNrm31 extend in the same direction, and in the case of FIG. 6B, VNrm31 extends in the opposite direction to VNrm12 and VNrm23.
However, calculation of the outer product will apparently increase calculation load.
As described above, according to the conventional method of calculating the intersection point of a triangle with a line segment, when calculating the intersection point of the same triangle with plural different line segments, the calculation need be performed again and again for each intersection point. As a result, entire calculation time becomes long, and it becomes difficult to realize high speed calculation.